package demo23;

/*
    给你一个链表数组，每个链表都已经按升序排列。

    请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class Test {

    public static void main(String[] args) {

    }

    public ListNode mergeKLists(ListNode[] lists) {
        //检查数组是否为空
        if(lists.length == 0){
            return null;
        }
        //定义结果链表，用来返回结果
        ListNode result = null;
        //定义当前用来排序的链表
        ListNode ln = null;
        //定义flag，用来判断此轮循环是否全部链表都为空
        boolean flag = false;
        boolean start = true;//这个标识符用来给result确定起点
        int min;//记录当前的最小值
        int index;//记录当前的最小值对应的链表下标
        while(!flag){
            flag = true;
            min = 0;//初始化最小值，这个值第一次必须赋值，之后才能用来比较
            index = 0;//同理，index也要初始化
            //遍历数组
            for (int i = 0; i < lists.length; i++) {
                //第二层遍历，用来比较当前的链表指向的值的最小值
                if(lists[i] == null){
                    continue;
                }else if(flag && lists[i] != null){
                    //扫描到第一个值，用来给min赋值，让他去比较别人的值
                    min = lists[i].val;
                    index = i;
                    flag = false;
                }else if(!flag && lists[i] != null && lists[i].val < min){
                    //找到更小的值，保存下标以及赋值
                    min = lists[i].val;
                    index = i;
                }
            }
            //如果这个链表数组还没有读完，移动对应下标的链表
            if(!flag){
                //是否初次赋值
                if(start){
                    ln = lists[index];
                    result = ln;
                    start = false;
                    //移动链表
                    lists[index] = lists[index].next;
                }else{

                    ln.next = lists[index];
                    //移动链表
                    lists[index] = lists[index].next;
                    ln = ln.next;
                }
            }
        }
        return result;
    }
}



  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }